/*
 抽象数据类型：单向的线性链表
*/



/*************************************引用部分*************************************/
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include "../StateCode.c"
/*************************************定义部分*************************************/
//结点
struct Node 
{
    int index;                                      //主键(自1以1增加)
    int data;                                       //数据域
    struct Node* next;                              //指针域
};

typedef struct Node Elem;

//链式线性表
struct LinkList
{
    struct Node* Node;                              //指向实际链表
    int length;                                     //链表长度(最后一个Node的index)
};

//获取index为i的Node
Status GetElem(struct LinkList* L,int i,Elem* e)
{
    Elem *p;                                        //游标
    if(i > L->length || i <= 0) exit(OVERFLOW);     //判断i的合法性
    p = L->Node;                                    //使p为首元素
    //将p作为游标进行遍历,最后一次循环使将index为i-1的Node.next赋予游标p
    for(int j=1;j<i;j++) p = p->next;
    *e = *p;                                         //反向传递数据
    return OK;
}

//在原第i个结点前插入新的Node（注意要更新后续Node.index，新元素之前的Node.index不变）
Status ListInsert(struct LinkList* L,int i,Elem* e)
{
    Elem* now;//游标，使用指针now来作为循环种子比使用实体p做循环种子更省性能
    //将新节点链接到原链表中（在if的两个分支中进行各种next指向修改）
    if(i == 1)                                       //如果在首部插入
    {
        e->next = L->Node;                          //原首部放到新结点后
        L->Node = e;                                //更新首部为新结点
    } 
    else if(i > 1 && i <= L->length+1)              //如果在中间或末尾插入
    {
        //利用now获取第i-1个结点
        now = L->Node;                              //使now为首元素
        //将now作为游标进行遍历,最后一次循环使将index为i-2的Node.next赋予游标now
        for(int j=1;j<i-1;j++) now = now->next;
        //循环完成后now便指向了第i-1个结点
        e->next = now->next;                        //将原第i结点接到新节点后
        now->next = e;                                //将新结点接到i-1后
    }
    else exit(OVERFLOW);                            //序号越界
    
    now = e;//为下面的index更新做准备
    /*
    第一次循环将把新插入的元素index进行更新
    后续循环将把新插入元素之后的各个元素进行index更新
    */
    while (now)
    {
        now->index = i++;
        now = now->next;//如果使用实体p做循环种子，这里赋值的代价更高
    }
    
    L->length++;                                    //更新长度

    return 0;
}

void PrintfInfo(struct LinkList* L)
{
    printf("index\t\taddress\t\tNextAddress\tdata\t\t\n");
    for (Elem* p = L->Node; p; p = p->next)
        printf("%d\t\t%d\t\t%d\t\t%d\n",p->index,p,p->next,p->data);
    printf("当前链表长度为：%d\n",L->length);
}

void TestInsert(struct LinkList* L)
{
    Elem e1,e2,e3,e4,e5;
    e1.data = 1111;e1.next=NULL;
    e2.data = 2222;e2.next=NULL;
    e3.data = 3333;e3.next=NULL;
    e4.data = 4444;e4.next=NULL;
    e5.data = 5555;e5.next=NULL;

    //空表插入
    ListInsert(L,1,&e1);
    //首部插入
    ListInsert(L,1,&e2);
    //尾部插入
    ListInsert(L,3,&e3);
    //中间插入
    ListInsert(L,2,&e4);
    //首部插入
    ListInsert(L,1,&e5);
    PrintfInfo(L);
}
/*************************************使用部分*************************************/
int main()
{
    SetConsoleOutputCP(65001);
    
    /*
    错误警告：这里对结构体初始化操作，系统不会自动将各项设为默认值，如果不手动设置会报错
    所以要手动设置
        L.Node = NULL;
        L.length = 0;
    */
    struct LinkList L;L.Node = NULL;L.length = 0;
    
    //调用测试函数，测试插入过程
    TestInsert(&L);
    
    system("pause");
    return 0;
}